\section{Experimental Results}
\label{sec:experiments}

We report our experimental results in two aspects.
First,  we test seven temporal expressive planners to show the performance of our CSTE planner.
Second, we study the effectiveness of our new techniques, lower bounding and variable branching schemes, by evaluating the efficiency of some MinCost solvers.

We run all experiments on a workstation with a dual core AMD Opteron
2200 processor and 8GB memory. Sun Java 1.6 and Python 2.6 run-time
systems are used. The time limit, for each instance, is set to 3600
seconds.

\subsection{Testing domains}
%TODO add brief domain descriptions here
Our experiments are done in a P2P domain we develop and several other CSTE
domains~\cite{Coles08}. Since the original domain definitions
in~\cite{Coles08} do not specify action costs, we examine those
actions and assign them reasonable numerical costs.
%Also, the number of problem instances is not sufficient.
Besides the original problems, we also generate some larger instances from a problem generator that we develop.
Note that we do not use all the domains in \cite{Coles08} because
some of them cannot scale to large problems (e.g. the Match domain),
and a few of them have variable-duration actions (e.g. the Caf\'{e}
domain). The following is a brief description of the domains that are included in the experiments.

\begin{enumerate}

\item \textbf{Peer-to-Peer Domain.} This domain models file transfers in Peer-to-Peer (P2P) networks. 
In Peer-to-Peer (P2P) networks, each computer, called a peer, may upload or download data from another.  
One critical issue in P2P networks is that a
substantial amount of inter-peer data communication traffic is
unnecessarily duplicated.
For those systems having consistent and intensive data sharing
between peers, communication latency is a potential bottleneck of
the overall network performance.
Mechanisms in network design, particularly proxy caching (a.k.a.
gateway caching), have been proposed to reduce duplicated data
transmission. Making a good use of the proxy cache is critical for
optimizing data transmission.

There are at least two different types of optimization in P2P networks.
The first one is approached from the user's point of view: each individual user wants all the data needed within the shortest possible time~\cite{Bhattacharya07}.  The other type is approached
from the point of view of a network service provider (such as an
Internet service provider (ISP)), who owns the network but does not
control individual peers. The main concern of a service provider is
to reduce the overall communication load.

These two performance metrics are typically conflicting. We
adopt performance metrics that lie in the middle of the
above mentioned two. Under these metrics, the network owner knows
each peer's needs, and the objective is to minimize the overall
makespan for all the data delivery for all peers and minimize the
total communication loads caused by different
actions including serving and downloading. The problem, when casted as a
planning problem, is temporally expressive.

The main constraint in this problem is to satisfy a file request
from a peer $p_1$, the same file has to be offered by another peer $p_2$.
$p_1$ can execute the {\em download} action to get the file, when 1)
there is a route between $p_1$ and $p_2$, and 2) $p_2$ is {\em serving} the file
throughout the transferring.  As such, these {\em serve} and {\em download} actions require
concurrency in any valid plan.

In addition, the proxy cache, which stores local caching files, will guarantee that, when $p_2$ is {\em
serving} a file, any peer who is routed to $p_2$ can {\em download}
the file very quickly. The upload bandwidth of a peer is typically much
narrower than its download bandwidth.  Therefore, enforced by the
optimality goal, the more peers downloading this particular file, the
larger the whole network's throughput will be, which brings about a
shorter time span in a solution plan.


In the {\em serve} action, for example, the processing time of a
file is proportional to its file size. We assume that by actively
sharing a file, the uploading peer uses up its uploading bandwidth.
That is, we assume that it cannot share another file simultaneously.
This assumption will not impose a real restriction as we can
introduce a time sharing scheme to extend the method we develop. A
predicate `serving' as one of the add-effects at the beginning
indicates that the peer is sharing a file. When sharing a file from a peer, the connected route will guarantee
that any other peers can get this file in a constant time (because
download speed is much faster), as long as it is routed to the
uploading peer.

The instances are generated randomly with different parameter settings, and the size
of each file object is randomly chosen from four to eight units.
The goal state for each instance is that each peer gets all
requested files. There are two types of problem settings with
different structures of network topology: one is loosely connected and
the other is highly connected. We assume that downloading is
cheaper than uploading and thus has a lower action cost.


\item \textbf{Matchlift domain.} 
In a Matchlift problem~\cite{Coles08}, an electrician enters an building to fix fuses during an outrage.
Since there is no light, the electrician needs to light a match to make it possible to repair in a dark room.
The required concurrencies between the action of lighting of a match, and the action of mending the fuse, make the problem temporally expressive.
Furthermore, before mending a fuse, the electrician may need to travel through the building by taking the elevator to the appropriate floor, and then find out and enter the correct room.

The original Matchlift domain~\cite{Coles08} has some flaws,
in which an electrician's position is not updated until the end of
a durative action. This can introduce a huge increase to the
number of electricians needed in Crikey2 and Crikey3, and eventually
electricians will exist everywhere.   To make Crikey2 and Crikey3 work
properly in this domain, we fix the flaws and use the fixed
version of Matchlift domain for this set of experiments.

We generate all instances randomly using different parameters for
the numbers of floors, rooms, matches and fuses. Each instance has
the same number of fuses and matches. In other words, these
instances are easier because we can always find a valid plan, such
that there is exactly one fixing action to be concurrent with a lighting match action. 
The action costs are set in a way that reflects how much energy is consumed. 
For example, actions for operating the elevator have higher costs than others.
\nop{
In the next subsection, we will have a variant domain
of Matchlift for another set of experiments, where the number of
match resources is less than the number of fuses to be fixed. As a
result, it will require more concurrencies than needed in these
simple Matchlift problem instances. 
}

\item \textbf{Matchlift-Variant domain.} 
The original Matchlift domain only requires one electrician to do the repairing.
Also, there are always enough matches available.
It is of a relatively weak form of required concurrency. 
We make a revised Matchlift domain (called Matchlift-Variant domain), which requires more concurrencies due to two changes.
%revised Matchlift domain (called Matchlift-Variant domain), , where the number of matches are limited.
%It requires multiple electricians work together to get all the broken fuses mended.
%We have also tested a set of instances in a revised Matchlift domain (called the Matchlift-Variant domain), which requires more concurrencies due to two changes.
First, the number of matches is less than the number of
fuses, so that multiple electricians need to share one
match.  Second, we reduce the duration of the `{\em mend\_fuse}' action so
that an electrician is able to conduct more mending actions during one match's
lighting, which also results in higher concurrencies.
The setting for actions costs is the same as the Matchlift domain.


\item \textbf{Driverslogshift domain.} 
The Driverslogshift domain~\cite{Coles08} is an extended version of the Driverslog domain from IPC-3~\cite{IPC3}.
It does similar things as those defined in the original Driverslog domain, as long as the worker is in the `{\em working}' status.
The {\em working} status, for each individual worker, is modeled as a durative action with a fixed duration.
After the {\em working} action is over, the worker needs to take a rest, which takes a constant duration.
The {\em working} action has to be concurrent with other actions by the worker.
This is why the problem is temporally expressive.
The possible actions of a worker, are driving trucks between locations, loading/unloading the trucks, and walking between locations.
The problem instances in the Driverslogshift domain
have much longer makespan than those in the Matchlift and P2P domains.

Compared with P2P and Matchlift, this domain has long durative
actions, which give rise to a long makespan.  Therefore, it is
relatively difficult to optimally solve instances in this domain. 
%These observations are reflected by our experimental results in Table~\ref{dr_result}. 
We set action costs to reflect the usage of energy: driving
a truck and loading/unloading the packages have higher action costs than other actions.
%The durations of some actions are changed from two to three to distinguish $\vdash, \dashv$ and $\leftrightarrow$ conditions and effects.

\end{enumerate}

%In P2P domain, since many uploading peers may get involved simultaneously in a typical download event, 
%it gives rise to a high concurrency.
High concurrencies in CSTE planning problems are very different from
most other temporal planning problems we have seen.  
%To better understand this high concurrency in temporal expressive planning
%domains, we examine temporal dependency here.
%When solution optimality is enforced in the P2P domain, concurrencies are naturally introduced in order to reduce the overall time span.
Figure~\ref{illuActions} illustrates the temporal dependencies (Definition~\ref{def:depc}) in
several instances from different domains.  All these instances have
comparable problem sizes.  The instance of P2P domain has 90 facts
and 252 actions, and the instance of Matchlift domain~\cite{Coles08}
has 216 facts and 558 actions.  Figure~\ref{illuActions} (I) is an
instance of the Trucks domain, which is temporally simple and thus
has all actions isolated. In Figure~\ref{illuActions} (II) for the
Matchlift domain, each action has up to two actions temporally
depending on it. In Figure~\ref{illuActions} (III) for the P2P
domain, each action has up to five actions temporally depending on it.

\begin{figure}%[tp]
 \centering
\scalebox{0.7}{\includegraphics{pic_actions.eps}}
\parbox{5in}{
\caption{\label{illuActions}\small  This figure partially
illustrates temporal dependencies of actions for instances in three
domains: Trucks, Matchlift and P2P. Each node represents an action.
Each edge represents a temporal dependency between two actions.}}
\end{figure}


\subsection{Results of temporal expressive planners}

Seven planners are tested and compared in our experiments. We test four temporally expressive planners:
Crikey2~\cite{Coles08:AIJ}~(runnable java JAR),
Crikey3~\cite{Coles08}~(static statically-linked binary for x86
Linux), LPG-c~\cite{Gerevi02} and Temporal Fast Downward (TFD)~\cite{Eyerich09}.
We also test SCP~\cite{huang09:ICAPS}, the basic SCP framework that does not minimize action costs. 
For each makespan, SCP uses MiniSAT2~\cite{Een:TAST-04} as its SAT solver to either prove
unsatisfiability or find a first satisfiable solution, disregarding the objective in the MinCost SAT formulation.
Further, still under the proposed SCP framework, we consider two strategies for
solving MinCost SAT instances and minimizing action costs: 
using our new BB-DPLL algorithm (denoted as SCP$^{bb}$), and
using a transformation from MinCost SAT to Max-SAT (introduced in ~\ref{appendix:maxsat}) and a generic Max-SAT solver SAT4J~\cite{sat4j} (denoted as SCP$^{max}$).
%The reduction from MinCost SAT to weighted partial Max-SAT is commonly used in solving MinCost SAT problems.
SAT4J is the winner of weighted partial Max-SAT (industrial track) in the
Max-SAT 2009 Competition~\cite{maxsat09}. In the SCP framework, SAT4J is
modified into an anytime solver, which keeps finding better solutions as it progresses.

%TFD fails in solving all instances in P2P and Driverslogshift domains. It solves all instances in Matchlift domain and four problem instances in Matchlift-Variant domain.


\subsubsection{The P2P domain}

We first experiment on a collection of instances in the P2P domain. 
The results are shown in Table~\ref{p2pResult}. If a planner is able to solve every instances, more
information is presented in the row `$\Sigma$' in Table~\ref{p2pResult}, which is the summation of solving time, makespan, or total action costs over all instances. 
This is for an easier comparison of different metrics
between the solvers. Crikey2, LPG-c and TFD are not included because they all fail to solve any instance.
We do not show makespan ("H") for SCP$^{bb}$ and SCP$^{max}$ in the tables since they give the same makespans as SCP.

\begin{table}%[hp]
\tbl{\small Experimental results in the P2P
domain. 
\label{p2pResult}}{
%\setlength{\tabcolsep}{3pt}
\small
\centering

\begin{tabular}{|l|l|rrr|rrr|rr|rr|}
\hline   \multirow{2}{*}{P} & \multirow{2}{*}{C,F}  & \multicolumn{3}{|c|}{Crikey3} & \multicolumn{3}{|c|}{SCP} & \multicolumn{2}{|c|}{SCP$^{max}$} & \multicolumn{2}{|c|}{SCP$^{bb}$} \\
\cline{3-12}
   &  & T & H & C &  T & H & C & T & C & T & C\\
\hline

1	&	4,4	&	0.1 	&	22	&	4110	&	4.9 	&	22	&	1980	 &	21.5 	&	520	&	60.4 	&	520	\\
2	&	5,5	&	0.1 	&	32	&	5190	&	19.1 	&	32	&	3560	 &	233.2 	&	800	&	157.5 	&	900	\\
3	&	6,6	&	0.2 	&	40	&	7340	&	134.0 	&	40	&	6000	 &	514.0 	&	1830	&	1156.8 	&	1160	\\
4	&	6,6	&	1.4 	&	72	&	12110	&	4.2 	&	27	&	2000	 &	15.2 	&	1320	&	12.0 	&	1320	\\
5	&	5,5	&	7.2 	&	100	&	20190	&	10.5 	&	34	&	3310	 &	76.4 	&	2200	&	253.3 	&	2320	\\
6	&	6,6	&	111.5 	&	150	&	30290	&	22.5 	&	39	&	4650	 &	618.3 	&	3300	&	193.2 	&	3550	\\
7	&	7,6	&	\multicolumn{3}{|c|}{Time Out}					&	61.6 	 &	54	&	6360	&	3513.6 	&	4300	&	1121.9 	&	4550	\\
8	&	6,7	&	287.7 	&	200	&	35340	&	122.1 	&	49	&	5430	 &	2624.2 	&	4060	&	3475.4 	&	4180	\\
9	&	7,7	&	\multicolumn{3}{|c|}{Time Out}					&	662.9 	 &	60	&	6960	&	2340.7 	&	5470	&	454.8 	&	6120	\\
10	&	5,25	&	\multicolumn{3}{|c|}{Time Out}					&	 757.8 	&	32	&	4010	&	388.2 	&	3610	&	228.2 	&	3500	 \\
11	&	6,18	&	\multicolumn{3}{|c|}{Time Out}					&	 45.1 	&	20	&	3200	&	210.9 	&	2700	&	58.2 	&	2700	 \\
12	&	6,24	&	\multicolumn{3}{|c|}{Time Out}					&	 88.9 	&	23	&	4190	&	162.4 	&	3610	&	114.0 	&	3600	 \\
13	&	6,30	&	\multicolumn{3}{|c|}{Time Out}					&	 1675.4 	&	31	&	5370	&	2714.2 	&	4720	&	1056.8 	&	4500	 \\
14	&	7,35	&	\multicolumn{3}{|c|}{Time Out}					&	 3303.0 	&	29	&	6770	&	2141.8 	&	5720	&	2788.0 	&	5600	 \\
\hline																							 
\multicolumn{2}{|c|}{$\Sigma$}			&	\multicolumn{3}{|c|}{n/a}					 &	6911.9 	&	492	&	63790	&	15574.6 	&	44160	&	11130.3 	 &	44520	\\



\hline
\end{tabular}
}
\Note{Column `P' is the instance ID. Columns `C' and `F' are the
numbers of peers and files, respectively, in the networks. Columns
`T', `H' and `C' are the solving time, makespan and total action
costs of solutions, respectively. Since SCP$^{max}$ and SCP$^{bb}$
find the same makespan as SCP does, there is no column `H' for
them. `Timeout' means that the solver runs out of the time limit of
3600s and `-' means no solution is found. If a planner solves all
the instances, row $\Sigma$ gives the sum of
all numbers in the corresponding column (`T', `H' or `C'). }
\end{table}


\normalsize

Instances 1 to 9 have simple topologies. Each peer is connected to
no more than two other peers. Also, in the initial state, only leaf
peers (those connected to only one peer) have files
to share. There are less concurrencies in this setting. Crikey2
fails to solve any instance in this category. Crikey3 solves seven
out of 14 instances. It is faster on two simpler instances but
slower than SCP on two other larger instances. Overall, the
makespans of solutions found by Crikey3 are up to five times longer
than those found by SCP. SCP also outperforms Crikey3 by up to 7
times in terms of the total action costs.

Instances 10 to 14 have more complicated network topologies.  Nearly
all nodes in these networks are connected to more than one other node.  Every
peer has some files needed by all others. In these cases, high
concurrencies are required to derive a plan. Both Crikey2 and
Crikey3 fail to solve any of these instances. Crikey3 times out
and Crikey2 reports no solution found.  It may be due to their
incompleteness.


SCP, SCP$^{bb}$ and SCP$^{max}$ solve all the instances. In
general, SCP$^{bb}$ runs longer than the other two. The total action
costs by SCP$^{max}$ and SCP$^{bb}$ are consistently lower (by up
to 4 times) than that of SCP.  Overall, SCP$^{bb}$ has comparable, if not better, performance
than SCP$^{max}$ in this domain; the former has a slightly
worse total action costs (0.8\% more) but much shorter solving time (28\%
shorter).


\subsubsection{The Matchlift domain}

The results on the Matchlift domain are in Table~\ref{ma_result}.  
On all instances, Crikey3 is the fastest to find solutions, but with
the lowest quality in terms of makespan. Surprisingly, Crikey3
finds the solutions with minimum action costs because for this
problem domain lower costs can be achieved under a longer makespan. TFD is the second fastest.
The solution quality by TFD is comparable to Crikey2, with slightly larger action cost but shorter makespan. 

SCP is the second fastest, with the optimal makespans, but higher total action costs than Crikey3.
Crikey2 is slightly faster, but also has worse makespan and total
action costs than SCP$^{max}$ and SCP$^{bb}$.
The solutions by SCP$^{max}$ and SCP$^{bb}$ have
comparable speed and exactly the same quality. They give optimal
makespan and only slightly worse action costs. LPG-c is the worst in this domain, with only two instances solved.

%The SCP framework
%(including SCP, SCP$^{max}$, and SCP$^{bb}$) is immune to this
%flaw, because it has the mutually exclusive actions encoded. As a
%result, SCP forbids two actions that delete the same fact to be
%executed at the same time.

\begin{table}%[hp]
\tbl{\small Experimental results in the
Matchlift domain. \label{ma_result}}{
\setlength{\tabcolsep}{1pt}

\footnotesize
\begin{tabular}{|l|l|rrr|rrr|rrr|rrr|rrr|rr|rr|}
\hline   \multirow{2}{*}{P} & \multirow{2}{*}{L,M,R,U}  & \multicolumn{3}{c|}{Crikey2} & \multicolumn{3}{|c|}{Crikey3} & \multicolumn{3}{|c|}{LPG-c} & \multicolumn{3}{|c|}{TFD} & \multicolumn{3}{|c|}{SCP} & \multicolumn{2}{|c|}{SCP$^{max}$} & \multicolumn{2}{|c|}{SCP$^{bb}$} \\
\cline{3-21}
  &  & T & H & C & T & H & C  & T & H & C & T & H & C & T & H & C & T & C & T & C\\

\hline
1	&	2,3,4,3	&	3.0 	&	13	&	332	&	0.1 	&	18	&	312	&	 0.1	&	17	&	352	&	0.0	&	13	&	332	&	2.6 	&	13	&	1052	 &	5.2 	&	332	&	2.6 	&	332	\\
2	&	3,2,9,2	&	0.7 	&	11	&	150	&	0.3 	&	14	&	130	&	 12.6	&	9	&	160	&	0.1	&	9	&	110	&	1.8 	&	9	&	 900	&	3.1 	&	110	&	1.8 	&	110	\\
3	&	2,3,4,3	&	2.9 	&	23	&	352	&	0.1 	&	28	&	332	&	 \multicolumn{3}{|c|}{-}					&	0.0	&	23	&	352	&	6.8 	 &	22	&	2032	&	16.0 	&	352	&	8.0 	&	352	\\
4	&	3,3,9,3	&	9.6 	&	19	&	452	&	0.1 	&	34	&	432	&	 \multicolumn{3}{|c|}{-}					&	0.0	&	19	&	452	&	7.2 	 &	18	&	1792	&	15.0 	&	452	&	7.3 	&	452	\\
5	&	3,4,9,4	&	52.8 	&	35	&	644	&	0.1 	&	43	&	524	&	 \multicolumn{3}{|c|}{-}					&	0.0	&	25	&	644	&	13.2 	 &	24	&	1664	&	29.9 	&	644	&	24.1 	&	644	\\
6	&	3,5,9,5	&	24.4 	&	39	&	906	&	1.4 	&	47	&	584	&	 \multicolumn{3}{|c|}{-}					&	8.3	&	34	&	1096	&	 20.6 	&	25	&	1936	&	49.7 	&	566	&	42.8 	&	566	\\
7	&	3,6,9,6	&	131.9 	&	37	&	804	&	0.4 	&	58	&	684	&	 \multicolumn{3}{|c|}{-}					&	1.2	&	42	&	1008	&	 88.3 	&	31	&	2316	&	195.5 	&	704	&	241.3 	&	704	\\
8	&	3,7,9,7	&	73.8 	&	42	&	854	&	1.9 	&	58	&	734	&	 \multicolumn{3}{|c|}{-}					&	20.8	&	35	&	1154	&	 131.0 	&	30	&	2566	&	400.3 	&	856	&	307.6 	&	856	\\
9	&	4,4,16,4	&	60.4 	&	39	&	644	&	0.1 	&	43	&	 624	&	\multicolumn{3}{|c|}{-}					&	7.3	&	39	&	1144	 &	26.7 	&	26	&	1884	&	65.9 	&	844	&	68.6 	&	844	 \\
10	&	4,5,16,5	&	234.1 	&	28	&	936	&	0.1 	&	58	&	 714	&	\multicolumn{3}{|c|}{-}					&	0.0	&	30	&	734	&	 55.6 	&	28	&	2144	&	109.4 	&	734	&	162.4 	&	734	\\
11	&	4,6,16,6	&	376.7 	&	47	&	1005	&	0.7 	&	58	&	 684	&	\multicolumn{3}{|c|}{-}					&	0.0	&	33	&	804	&	 152.0 	&	31	&	2334	&	265.7 	&	804	&	413.0 	&	804	\\
\hline																																									 
\multicolumn{2}{|c|}{$\Sigma$}			&	970.4 	&	333	&	7079	&	 5.3 	&	459	&	5754	&	\multicolumn{3}{|c|}{-}					&	 37.8	&	292	&	7830	&	505.9 	&	257	&	20620	&	1155.6 	&	 6398	&	1279.4 	&	6398	\\
\hline
\end{tabular}
}
\Note{The numbers in Columns `L', `M', `R' and `U'
represent the numbers of floors, matches, rooms and fuses,
respectively, which are used in generating the instances.}
\end{table}
\normalsize







%YC: This instance 12 is weird. If you add it by yourself,
% consider deleting it. You already have the variant domain
% in the next subsection

%RH2:  Instance 12 is removed by Yixin's suggestion
%Because Instance 12 has less matches than fuses (5 matches and 6
%fuses), it forces two electricians to cooperate
% and share one single match while fixing fuses.
% This setting asks for higher concurrency than those simpler
% instances. Both Crikey2 and Crikey3 failed to find out a
%valid solution.


\subsubsection{The Matchlift-Variant domain}


The results are shown in Table~\ref{mar_result}. All instances are
generated with increasing numbers of fuses and electricians.
All the other settings, such as the number of floors, rooms and matches, are randomly set.
Instances with the same number of
fuses and electricians may still have different degrees of
concurrency, due to different numbers of matches and other
resources. For example, although Instances 7 and 8 have the same
parameters, Instance 8 is more difficult than Instance 7 due to
different ways the fuses are distributed among rooms.


\begin{table}%[hp]
\tbl{ \small Experimental results in the
Matchlift-Variant domain.  \label{mar_result}
}{
\setlength{\tabcolsep}{1pt}

\footnotesize
\begin{tabular}{|l|l|rrr|rrr|rrr|rrr|rrr|rr|rr|}
\hline   \multirow{2}{*}{P} & \multirow{2}{*}{L,M,R,U}  & \multicolumn{3}{c|}{Crikey2} & \multicolumn{3}{|c|}{Crikey3} & \multicolumn{3}{|c|}{LPG-c} & \multicolumn{3}{|c|}{TFD} & \multicolumn{3}{|c|}{SCP} & \multicolumn{2}{|c|}{SCP$^{max}$} & \multicolumn{2}{|c|}{SCP$^{bb}$} \\
\cline{3-21}
  &  & T & H & C & T & H & C  & T & H & C & T & H & C & T & H & C & T & C & T & C\\

\hline


1	&	2,2,4	&	10.9 	&	14	&	220	&	5.1 	&	17	&	200	&	 \multicolumn{3}{c|}{-}					&	\multicolumn{3}{c|}{-}					 &	2.5 	&	13	&	840	&	8.1 	&	220	&	2.4 	&	220	\\
2	&	2,1,4	&	147.7 	&	13	&	374	&	7.5 	&	16	&	334	&	 0.4	&	13	&	354	&	\multicolumn{3}{c|}{-}					&	 1.7 	&	13	&	1294	&	4.2 	&	254	&	1.7 	&	254	\\
3	&	2,3,5	&	6.1 	&	19	&	392	&	0.1 	&	23	&	372	&	 \multicolumn{3}{c|}{-}					&	0.5	&	19	&	414	&	 5.7 	&	18	&	1336	&	12.3 	&	392	&	5.7 	&	392	\\
4	&	2,2,5	&	106.0 	&	25	&	444	&	41.8 	&	27	&	424	&	 460.9	&	21	&	354	&	\multicolumn{3}{c|}{-}					&	 6.9 	&	21	&	1624	&	22.8 	&	342	&	6.7 	&	342	\\
5	&	2,4,6	&	20.3 	&	23	&	482	&	0.1 	&	33	&	462	&	 \multicolumn{3}{c|}{-}					&	5.9	&	29	&	492	&	9.4 	 &	22	&	1962	&	23.1 	&	482	&	16.0 	&	482	\\
6	&	2,2,6	&	121.6 	&	25	&	464	&	42.0 	&	27	&	444	&	 0.1	&	33	&	362	&	\multicolumn{3}{c|}{-}					&	 5.9 	&	21	&	1454	&	22.7 	&	362	&	7.2 	&	362	\\
7	&	3,2,7	&	\multicolumn{3}{c|}{-}					&	 \multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					 &	\multicolumn{3}{c|}{-}					&	9.9 	&	16	&	1636	 &	37.1 	&	396	&	10.0 	&	396	\\
8	&	3,2,7	&	167.1 	&	17	&	290	&	\multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					&	 \multicolumn{3}{c|}{-}					&	53.3 	&	16	&	1484	&	 292.7 	&	290	&	52.8 	&	290	\\
9	&	3,4,8	&	\multicolumn{3}{c|}{Time Out}					&	 \multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					 &	104.7	&	33	&	734	&	22.8 	&	22	&	1668	&	2582.7 	&	 534	&	52.5 	&	534	\\
10	&	3,2,8	&	\multicolumn{3}{c|}{Time Out}					&	 \multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					 &	\multicolumn{3}{c|}{-}					&	94.3 	&	20	&	1726	 &	488.7 	&	416	&	94.6 	&	416	\\
11	&	4,3,8	&	\multicolumn{3}{c|}{Time Out}					&	 \multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					 &	\multicolumn{3}{c|}{-}					&	361.4 	&	16	&	1398	 &	543.2 	&	476	&	366.1 	&	476	\\
12	&	4,1,8	&	\multicolumn{3}{c|}{Time Out}					&	 \multicolumn{3}{c|}{Time Out}					&	\multicolumn{3}{c|}{-}					 &	\multicolumn{3}{c|}{-}					&	3.1 	&	13	&	1008	 &	8.9 	&	358	&	2.3 	&	358	\\
\hline																																									 
\multicolumn{2}{|c|}{$\Sigma$}			&	\multicolumn{3}{|c|}{n/a}					 &	\multicolumn{3}{|c|}{n/a}					&	 \multicolumn{3}{|c|}{n/a}					&	\multicolumn{3}{|c|}{n/a}					 &	576.9 	&	211	&	17430	&	4046.3 	&	4522	&	618.1 	&	 4522	\\


\hline
\end{tabular}
}
\Note{The numbers in columns `E', `M' and `U' represent
the numbers of electricians, matches, and fuses, respectively.
`Timeout' means that the solver runs out of the time limit of
3600s and `-' means no solution is found.}
\end{table}

\normalsize

As shown by our experimental results in Table~\ref{mar_result}, SCP
finds optimal makespan on all instances tested, whereas
Crikey2 and Crikey3 run out of time on most instances and generate
suboptimal plans on a few instances they finished.  For the
instances they solved, Crikey3 has the worst makespan.
Except on very small instances, we can see that SCP not only finds the
optimal solutions, but also runs faster than Crikey2 and
Crikey3.

In this domain, SCP$^{bb}$ runs slightly slower than SCP, but finds
solutions with significantly lower total action costs than the
latter. As a comparison, although on certain instances SCP$^{max}$
can find solutions with exactly the same quality, it runs up to six
times slower than SCP$^{bb}$ to reach those solutions.
Both LPG-c and TFD are not good in this domain, with three instances solved. 

\nop{
The results on Instances 11 and 12 are special and interesting.
These two instances are generated under the same parameter setting
as other instances, except for the number of matches. Instance 12
has a unique optimal solution, where four electricians
need to cooperate with each other perfectly to fix all the fuses.
%Instance 12 turns out to be more difficult than Instance 11 for
%Crikey2, because it requires more
%YC: from the table, Crikey2 did not solve instance 11. please check!
%concurrencies. As a result, Crikey2 solves Instance 11 but fails on
%Instance 12.
Instance 12 is much easier than Instance 11 for SCP.
SCP solves Instance 12 in just about three
seconds, while spends more than 360 seconds on Instance 11.
}




\subsubsection{The Driverslogshift domain}

\begin{table}%[hp]
\tbl{\small Experimental results in the
Driverslogshift domain.\label{dr_result} }{
\setlength{\tabcolsep}{2pt}
\footnotesize
\begin{tabular}{|l|l|rrr|rrr|rrr|rrr|rr|rr|}
\hline   \multirow{2}{*}{P} & \multirow{2}{*}{D,P,T}  & \multicolumn{3}{c|}{Crikey2} & \multicolumn{3}{|c|}{Crikey3} & \multicolumn{3}{|c|}{LPG-c} & \multicolumn{3}{|c|}{SCP} & \multicolumn{2}{|c|}{SCP$^{max}$} & \multicolumn{2}{|c|}{SCP$^{bb}$} \\
\cline{3-18}
  &  & T & H & C & T & H & C & T & H & C & T & H & C & T & C & T & C\\
\hline


1	&	2,2,2	&	16.7$^*$ 	&	122	&	2850	&	0.1 	&	224	&	 2600	&	336.7	&	712	&	4650	&	182.7 	&	102	&	2660	&	 306.4 	&	2700	&	216.0 	&	1760	\\							
2	&	2,2,2	&	4.0 	&	122	&	1450	&	0.1 	&	122	&	 1400	&	2.2	&	244	&	2750	&	202.6 	&	122	&	2670	&	 500.0 	&	1450	&	551.8 	&	775	\\							
3	&	2,3,2	&	18.8 	&	122	&	4450	&	0.1 	&	225	&	 3200	&	712.5	&	346	&	4900	&	232.1 	&	122	&	4505	&	 451.5 	&	3900	&	231.8 	&	1935	\\							
4	&	2,3,2	&	19.8 	&	122	&	3950	&	0.2 	&	323	&	 3700	&	365.3	&	122	&	4600	&	233.9 	&	122	&	3575	&	 450.0 	&	4050	&	233.3 	&	1935	\\							
5	&	2,4,2	&	38.3 	&	102	&	3900	&	0.1 	&	238	&	 3600	&	653.0	&	224	&	4100	&	241.7 	&	102	&	1940	&	 589.7 	&	3900	&	629.4 	&	2010	\\							
6	&	2,4,3	&	10.4$^*$ 	&	122	&	2700	&	0.1 	&	326	&	 2500	&	85.8	&	224	&	4300	&	217.8 	&	118	&	6020	&	 402.1 	&	3700	&	218.7 	&	1930	\\							
7	&	3,6,3	&	201.4 	&	102	&	6400	&	0.2 	&	102	&	 4700	&	9.3	&	102	&	5000	&	432.5 	&	102	&	3330	&	 693.2 	&	5800	&	422.6 	&	3020	\\							
8	&	3,6,4	&	180.4 	&	102	&	7500	&	0.2 	&	125	&	 5050	&	2.2	&	102	&	5150	&	443.5 	&	102	&	7330	&	 678.6 	&	5900	&	423.8 	&	2530	\\							
9	&	3,7,3	&	159.5$^*$ 	&	102	&	6900	&	0.2 	&	125	&	 5050	&	15.9	&	102	&	4600	&	443.5 	&	102	&	4940	&	 677.3 	&	6100	&	434.0 	&	3080	\\							
\hline																																										 
\multicolumn{2}{|c|}{$\Sigma$}			&	649.3 	&	1018	&	40100	 &	1.3 	&	1810	&	31800	&	2183.01	&	2178	&	40050	&	 2630.4 	&	994	&	36970	&	4748.8 	&	37500	&	3361.3 	&	18975	 \\
\hline
\end{tabular}
}
\Note{The numbers in columns `D', `P' and `T' represent
the numbers of drivers, packages, and trucks, respectively. The
result marked with a `$^*$' means that the solution is invalid.}
\end{table}

Crikey3 again is the fastest among all planners. Its makespans,
however, are much worse than that of all others. As shown in Table
~\ref{dr_result}, the optimal makespans of the instances tested,
provided by SCP, SCP$^{max}$ and SCP$^{bb}$, are typically much
shorter than those by Crikey3. For example, the optimal makespan
for Instance 4 in Table~\ref{dr_result} is about one third of the
makespan reported by Crikey3. 
LPG-c finds solutions with solving times that are similar to SCP's, which is much slower than Crikey2 and Crikey3. 
Its solution quality is however the worst: its makespan is comparable to Crikey3, and total action costs is about the same to Crikey2. 
TFD is not included because it fails to solve any instance in this domain. 

Crikey2, as a sub-optimal planner,
is able to generate solutions of the same makespan as what our planners
found on most instances in this domain.  However, a close
examination leads us to believe that some of the solutions produced by
Crikey2 are incorrect. For example, it may generate solutions with
fragments of invalid action sequence as follows:

{
\begin{flushleft}
\begin{Verbatim}[frame=lines, samepage=true]
 ...
 102:(REST driver2) [20.00]
 102:(DRIVE-TRUCK truck1 s1 s0 driver2)[10.00]
 ...
\end{Verbatim}
\end{flushleft}
}

Such a plan requires the same driver to perform two
actions, \textsl{REST} and \textsl{DRIVE}, at the same time. It
apparently violates the domain specification.
%, which defines that
%a \textsl{DRIVE} action needs to be concurrent with a \textsl{WORK} action and
%a \textsl{WORK} action is mutual exclusive with a \textsl{REST}
%action.

In terms of action costs, SCP$^{bb}$ is by far the best, much better than the plans found by Crikey2, Crikey3, SCP, and SCP$^{max}$, whose have similar quality.
SCP$^{bb}$ is also much more efficient than SCP$^{max}$.

Overall, our experiments on all the CSTE domains show that: 1) Our planner solves the problem efficiently,
comparing favorably with the existing temporally expressive planners, and 2) The BB-DPLL algorithm is competitive with, if
not better than, the Max-SAT approach for SAT-based CSTE planning.


\subsubsection{Number of variables and clauses}

One may concern about the size of SAT encoding and the time cost
of SCP, which are issues that any optimal planner faces. In
Table~\ref{var_result}, we list the numbers of variables and clauses
of each instance (in the last iteration).
We show data in the P2P and the
Matchlift-Variant domains. The solving time is presented to show the
difficulty of the instances.

Similar to other SAT problems, it is obvious that the size of
encoding does not necessarily reflect the complexity of a problem. For
example, the numbers of variables or clauses of Instance 3 in the P2P
domain are both slightly smaller than those of Instance 4.
However, Instance 3 is solved 30 times slower than Instance 4.



\begin{table}%[hp]
\tbl{\small  Numbers of variables and
clauses in P2P domain and Matchlift-Variant domain. \label{var_result} }{
\small
\begin{tabular}{|l|r|r|r||r|r|r|}
\hline   \multirow{2}{*}{P}  & \multicolumn{3}{|c|}{P2P} & \multicolumn{3}{|c|}{Matchlift-Variant}  \\
\cline{2-7}
 &  \#VAR   & \#Clause & T & \#VAR & \#Clause  & T\\

\hline

1   &   498 &   1032    &   4.9     &   3632    &   13502   &   2.4     \\
2   &   1538    &   4161    &   19.1    &   2583    &   8892    &   1.7     \\
3   &   5799    &   17378   &   134.0   &   7122    &   33414   &   5.7     \\
4   &   7076    &   19961   &   4.2     &   6431    &   29363   &   6.7     \\
5   &   19230   &   58521   &   10.5    &   11608   &   66468   &   16.0    \\
6   &   47046   &   152042  &   22.5    &   6798    &   31826   &   7.2     \\
7   &   95080   &   410983  &   61.6    &   7524    &   34137   &   10.0    \\
8   &   59526   &   198216  &   122.1   &   7524    &   37663   &   52.8    \\
9   &   91482   &   344504  &   662.9   &   18513   &   128674  &   52.5    \\
10  &   95080   &   410983  &   757.8   &   10043   &   52352   &   94.6    \\
11  &   59526   &   198216  &   45.1    &   13601   &   75843   &   366.1   \\
12  &   91482   &   344504  &   88.9    &   5449    &   21113   &   2.3     \\
\hline
\end{tabular}
}
\Note{Column `\#VAR' is the number of variables, column `\#Clause' is the number of
clauses and column `T' is the overall solving time by SCP.}
\end{table}
\normalsize


In general, the encoding of SCP on current problem instances
may have up to hundreds of thousands of variables, which are within the
capability of current SAT solvers. Various improvements to SAT-based
planning could also be applied to SCP. We plan to further study
techniques such as encoding in new formulations~\cite{Robinson08,huang:AAAI10}
and deriving constraint-based pruning clauses~\cite{Chen09}.


\subsection{Effectiveness of lower bounding and variable branching techniques}
\label{sec:opt-res}


\begin{figure}%[tp]
  %\centering
\begin{center}
    \subfigure[P2P]{\includegraphics[scale=0.3]{./figure/data_p2p-cost.eps}}
    \hspace{3mm}
    \subfigure[Matchlift]{\includegraphics[scale=0.3]{./figure/data_matchlift-cost.eps}}\\
    \vspace{2mm}
    \subfigure[Matchlift-Variant]{\includegraphics[scale=0.3]{./figure/data_matchliftv-cost.eps}}
    \hspace{3mm}
    \subfigure[Driverslogshift]{\includegraphics[scale=0.3]{./figure/data_driverlog-cost.eps}}
\caption{\label{fig:cost-1}  \small Comparisons of the total action costs by
different solvers, where ``no-opt" represents the solution found
by MiniSat. The y-axis shows the solution quality in terms of total
action cost.}
\end{center}
\end{figure}


\begin{figure}%[tp]
  %\centering
\begin{center}
    \subfigure[P2P]{\includegraphics[scale=0.3]{./figure/data_p2p-time.eps}}
    \hspace{3mm}
    \subfigure[Matchlift]{\includegraphics[scale=0.3]{./figure/data_matchlift-time.eps}}\\
    \vspace{2mm}
    \subfigure[Matchlift-Variant]{\includegraphics[scale=0.3]{./figure/data_matchliftv-time.eps}}
    \hspace{3mm}
    \subfigure[Driverslogshift]{\includegraphics[scale=0.3]{./figure/data_driverlog-time.eps}}
\caption{\label{fig:time-1}  \small Comparison of the anytime performance
of different solvers.}
\end{center}
\end{figure}

We implement our SCP$^{bb}$ solver based on MiniSAT.
We study the effectiveness of our new techniques by evaluating the efficiency of several solvers:
the original MiniSAT that quits at the first solution (no-opt), a
basic BB-DPLL algorithm using $h(\psi)=0$ and the original VSIDS
branching heuristic (base), BB-DPLL using the proposed lower bounding function~(+h), BB-DPLL using a new variable
branching heuristic~(+heu), BB-DPLL using +h and +heu options
(all), and MinCostChaff~(MCC), an existing MinCost SAT solver that incorporates many modern SAT techniques~\cite{Fu06}.
Comparisons are conducted in four domains: P2P, Matchlift, Matchlift-Variant and Driverslogshift.
The results are shown in Figures~\ref{fig:cost-1} and~\ref{fig:time-1}.
Detailed results are given in Tables in ~\ref{appendix:cost-time}.

Figures~\ref{fig:cost-1} and ~\ref{fig:time-1} show the solution quality and the solving time of different strategies.
For each strategy, we show the minimum total action costs found and the solving time for finding the best solution in 3600 seconds. 
We can see that the basic BB-DPLL algorithm finds solutions with much smaller total action cost than the original MiniSAT (see Figure~\ref{fig:cost-1}). 
By using the lower bounding function, BB-DPLL finds better solutions than the basic algorithm (see subfigures (a) and (d) in Figure~\ref{fig:cost-1}).
Since computing lower bounding function consumes extra time, it usually spends more solving time than the basic algorithm (see Figure~\ref{fig:time-1}).
From the cost results in subfigures (a) and (b) of Figure~\ref{fig:cost-1} and the solving time results in Figure~\ref{fig:time-1}, we can see that with the new variable branching scheme, BB-DPLL finds even better solutions faster than the basic algorithm.
Finally, combining the two strategies leads to the best performance, finding the best quality solutions faster than other strategies on most problem instances.
In Matchlift and Matchlift-Variant domains, since it is easy to find optimal solutions, all variants of BB-DPLL find the same solutions in the time limit.

In Figure~\ref{fig:cost-1}, we can see that MinCostChaff can find high-quality solutions on most of the problems tested.
However, MinCostChaff uses much more solving time to find the best solutions than our algorithm, and fails on some large problems~(P2P-10, 12, 13, 14, Matchlift-7, 8, 11, Matchlift-Variant-11 and Driverslogshift-7, 8, 9) (see Figure~\ref{fig:time-1}).
A possible reason is that its lower bounding function, which is not tailored for planning problems, is less effective on large problems.
%Detailed results are given in the last columns of Tables~\ref{tb:p2p}, \ref{tb:matchlift}, \ref{tb:matchliftv} and~\ref{tb:driverlog}~(See \ref{appendix:cost-time}).
%Note that since MinCostChaff does not output the solving time of each solution, we only present its total action costs of solutions.
%Note that since MinCostChaff does not output the solving time of solutions, we only give the results of total action costs.

In conclusion, both the lower bounding function and new variable branching scheme can significantly improve the basic
BB-DPLL algorithm, and combining these techniques leads to the best performance.
Furthermore, the BB-DPLL algorithm is much more efficient than MinCostChaff due to its effective bounding function, especially on large problems.
Detailed results for all instances in the testing CSTE planning domains are presented in Tables~\ref{tb:p2p},~\ref{tb:matchlift},~\ref{tb:matchliftv} and~\ref{tb:driverlog}.

\nop{
Figure~\ref{fig:time-1} shows the solving time of finding the best solutions.
We can see that ``+h" usually spends more time than ``base" because it needs extra time to computing the lower bound.
Compare to ``base", ``+heu" can largely reduce the solving time which proves that the new variable branching heuristic can significantly improve search efficiency.
Combing both techniques achieves a 
}

\nop{
Figure~\ref{fig:time-1} shows the anytime performance of the four
variants of BB-DPLL in several CSTE planning domains. For each
domain, we solve a number of instances. For each instance, we record
all solutions found as the search progresses and normalize their total
action costs into range $[0,1]$.
For a particular instance, ``0" denotes the best total action costs ever found, and ``1" refers to the worst one.
Each point gives the solving time and total action costs of a solution plan.
All connected points in the same line represent all solutions found by certain solver on one problem which shows the anytime performance of the solver on this problem.
We can see that the basic BB-DPLL has the worst anytime performance. Both our new branching heuristic and the
lower bounding function can improve the performance, and combing
both techniques further improves search performance.
%makes the solver find high-quality solutions in a fastest manner.
}

\nop{By comparing the behaviors of different techniques, we can see
that regarding the total action costs of the first solution, new
variable branching scheme~(+heu) is consistently better than basic
BB-DPLL; it also finds the optimal solution much faster. Using lower
bounding function, MC-SAT usually has better total action costs than
basic BB-DPLL. Finally, to use both BB-DPLL heuristic and the lower
bounding function results in the best strategy: the best solution
quality and the fastest solving time. }

